#include "algo.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>


int cmp_int(int *p1, int *p2)
{
    if (*p1 < *p2)
        return -1;
    else if (*p1 > *p2)
        return 1;
    return 0;
}

int cmp_double(double *p1, double *p2)
{
    if (*p1 < *p2)
        return -1;
    else if (*p1 > *p2)
        return 1;
    return 0;
}

void test_merge_sort()
{
    printf("======test_merge_sort\n");

    const int NUM = 1000;
    double int_array[NUM];

    int i;
    for (i = 0; i < NUM; ++i)
        int_array[i] = 1.0d * rand() / rand();

    printf("======before sort\n");
    for (i = 0; i < NUM; ++i)
        printf("%f  ", int_array[i]);

    merge_sort(int_array, sizeof(double), 0, NUM - 1, (cmp_func)cmp_double);

    printf("\n======after sort\n");
    for (i = 0; i < NUM; ++i)
        printf("%f  ", int_array[i]);

    printf("\n======over\n");
}

void test_max_subarray()
{
    printf("======test_max_subarray\n");

    const int NUM = 20;
    long array[NUM];

    int i;
    for (i = 0; i < NUM; ++i)
    {
        int sign = rand() % 2;
        array[i] = (rand() % NUM) * (sign ? sign : -1);
    }

    printf("======raw array\n");
    for (i = 0; i < NUM; ++i)
        printf("%d  ", array[i]);

    Sub_Array sa = search_max_subarray(array, 0, NUM - 1);

    printf("\n======max sub array\n");
    for (i = sa.left; i <= sa.right; ++i)
        printf("%d  ", array[i]);
    printf("\n======sum is %d\n", sa.value);
}

void test_heap_sort()
{
    printf("======test_heap_sort\n");

    const int NUM = 30;
    int int_array[NUM];

    int i;
    for (i = 0; i < NUM; ++i)
        int_array[i] = rand() % 1000;

    printf("======before sort\n");
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    heap_sort(int_array, sizeof(int), NUM, (cmp_func)cmp_int);

    printf("\n======after sort\n");
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    printf("\n======over\n");
}

void test_heap_extract_max()
{
    printf("======test_heap_extract_max\n");

    const int NUM = 30;
    int int_array[NUM];

    int i;
    for (i = 0; i < NUM; ++i)
        int_array[i] = rand() % 1000;

    printf("======before build heap\n");
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    printf("\n======extract max\n");
    build_heap(int_array, sizeof(int), NUM, (cmp_func)cmp_int);
    int *max = NULL;
    long len = NUM;
    while (len)
    {
        max = heap_extract_max(int_array, sizeof(int), &len, (cmp_func)cmp_int);
        printf("%d  ", *max);
    }

    printf("\n======over\n");
}

void test_heap_change_key()
{
    printf("======test_heap_change_key\n");

    const int NUM = 30;
    int int_array[NUM];

    int i;
    for (i = 0; i < NUM; ++i)
        int_array[i] = rand() % 1000;

    printf("======before build heap\n");
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    printf("\n======build heap\n");
    build_heap(int_array, sizeof(int), NUM, (cmp_func)cmp_int);
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    printf("\n======change key\n");
    long idx = rand() % NUM;
    int key = rand() % 100;
    heap_change_key(int_array, sizeof(int), idx, &key, (cmp_func)cmp_int);
    printf("index=%d  key=%d\n", idx, key);
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    printf("\n======over\n");
}

void test_heap_insert()
{
    printf("======test_heap_insert\n");

    const int NUM = 30;
    int int_array[NUM];

    int i;
    for (i = 0; i < NUM - 1; ++i)
        int_array[i] = rand() % 1000;

    printf("======before build heap\n");
    for (i = 0; i < NUM - 1; ++i)
        printf("%d  ", int_array[i]);

    printf("\n======build heap\n");
    build_heap(int_array, sizeof(int), NUM - 1, (cmp_func)cmp_int);
    for (i = 0; i < NUM - 1; ++i)
        printf("%d  ", int_array[i]);

    printf("\n======insert key\n");
    int key = rand() % 100;
    heap_insert(int_array, sizeof(int), NUM - 1, &key, (cmp_func)cmp_int);
    printf("key=%d\n", key);
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    printf("\n======over\n");
}

void test_quick_sort()
{
    printf("======test_quick_sort\n");

    const int NUM = 30;
    int int_array[NUM];

    int i;
    for (i = 0; i < NUM; ++i)
        int_array[i] = rand() % 1000;

    printf("======before sort\n");
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    quick_sort(int_array, sizeof(int), 0, NUM - 1, (cmp_func)cmp_int);

    printf("\n======after sort\n");
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    printf("\n======over\n");
}

void test_select_Ith()
{
    printf("======test_select_Ith\n");

    const int NUM = 10;
    int int_array[NUM];

    int i;
    for (i = 0; i < NUM; ++i)
        int_array[i] = rand() % 100;

    printf("======raw array\n");
    for (i = 0; i < NUM; ++i)
        printf("%d  ", int_array[i]);

    i = 5;
    void *result = select_Ith(int_array, sizeof(int), 0, NUM - 1, i, (cmp_func)cmp_int);

    printf("\n======result\n");
    if (result == NULL)
        printf("not found\n");
    else
        printf("#[%d]=%d\n", i, *(int*)result);

    printf("\n======over\n");
}


typedef struct
{
    int key;
    struct binary_tree_node node;
} Tree_Node;

int compare_tree_node(struct binary_tree_node *n1, struct binary_tree_node *n2)
{
    Tree_Node *p1 = container_of(n1, Tree_Node, node);
    Tree_Node *p2 = container_of(n2, Tree_Node, node);
    if (p1->key < p2->key)
        return -1;
    else if (p1->key > p2->key)
        return 1;
    return 0;
}

void print_tree(struct binary_tree_node *tree, int indent, const char* tag)
{
    int i;

    if (tree)
    {
        Tree_Node *p = container_of(tree, Tree_Node, node);
        for (i = 0; i < indent; ++i)
            printf("    ");
        printf("%d%s\n", p->key, tag);
        ++indent;
        print_tree(tree->left, indent, "(L)");
        print_tree(tree->right, indent, "(R)");
    }
    /*else
    {
        for (i = 0; i < indent; ++i)
            printf("    ");
        printf("NULL%s\n", tag);
    }*/
}

void test_binary_tree()
{
    struct binary_tree_node *root = NULL;
    const int NUM = 50;
    int i;
    Tree_Node *tnode;

    for (i = 0; i < NUM; ++i)
    {
        tnode = malloc(sizeof(Tree_Node));
        init_binary_tree_node(&tnode->node);
        tnode->key = rand() % 1000;
        tree_insert(&root, &tnode->node, compare_tree_node);
    }

    i = 0;
    print_tree(root, i, "");
}

/******* test black-red tree ****************/

typedef struct
{
    int key;
    struct rb_tree_node node;
} RB_Tree_Node;

int compare_rb_tree_node(struct rb_tree_node *n1, struct rb_tree_node *n2)
{
    RB_Tree_Node *p1 = container_of(n1, RB_Tree_Node, node);
    RB_Tree_Node *p2 = container_of(n2, RB_Tree_Node, node);
    if (p1->key < p2->key)
        return -1;
    else if (p1->key > p2->key)
        return 1;
    return 0;
}

void print_rb_tree(struct rb_tree_node *tree, int indent, const char* tag)
{
    int i;

    if (tree)
    {
        RB_Tree_Node *p = container_of(tree, RB_Tree_Node, node);
        for (i = 0; i < indent; ++i)
            printf("    ");
        printf("%d[%s]%s\n", p->key, tree->color ? "B" : "R", tag);
        ++indent;
        print_rb_tree(tree->left, indent, "(<)");
        print_rb_tree(tree->right, indent, "(>)");
    }
    /*else
    {
        for (i = 0; i < indent; ++i)
            printf("    ");
        printf("NULL%s\n", tag);
    }*/
}

void test_rb_tree()
{
    struct rb_tree_node *root = NULL;
    const int NUM = 5000, FAC = 5;
    RB_Tree_Node *del[NUM/FAC + 1];
    int i, j = 0;
    RB_Tree_Node *tnode, *z = NULL;

    for (i = 0; i < NUM; ++i)
    {
        tnode = malloc(sizeof(RB_Tree_Node));
        init_rb_tree_node(&tnode->node);
        tnode->key = rand();
        rb_insert(&root, &tnode->node, compare_rb_tree_node);

        if (i % FAC == 0)
            del[j++] = tnode;
    }

    print_rb_tree(root, 0, "");

    printf("\n\n========================= now delete ===================\n\n");
    //rb_delete(&root, &z->node);
    for (i = 0; i < j; ++i)
        rb_delete(&root, &del[i]->node);
    print_rb_tree(root, 0, "");
}


void test_lcs()
{
    const long xlen = 1000;
    const long ylen = 1045;
    char x[xlen], y[ylen];
    LCS_sub sub[xlen];
    long cslen;
    int i;

    printf("\n============== x =============\n");
    for (i = 0; i < xlen; ++i)
    {
        x[i] = rand() % 26 + 'A';
        printf("%c ", x[i]);
    }

    printf("\n============== y =============\n");
    for (i = 0; i < ylen; ++i)
    {
        y[i] = rand() % 26 + 'A';
        printf("%c ", y[i]);
    }

    LCS_result lcs = lcs_length(x, y, xlen, ylen);
    cslen = get_lcs(lcs.b, x, xlen, ylen, sub);

    printf("\n============== LCS =============\n");
    printf("length: %d\n", cslen);
    for (i = 0; i < cslen; ++i)
    {
        printf("(%d, %d, %c)  ", sub[i].i, sub[i].j, sub[i].w);
    }

    free_lcs(lcs, xlen, ylen);

    printf("\n============== over =============\n");
}


void test_b_tree()
{
    const int NUM = 505674;
    int d[NUM], cnt = 0;
    int i, j, key;
    struct B_Tree_Node *r = btree_create();

    printf("===========test_b_tree=========\n");

    for (i = 0; i < NUM; ++i)
	{
		j = rand();
        r = btree_insert(r, j);
		if (i == 24873)
			key = j;

        if (i % 17 == 0)
            d[cnt++] = j;
	}

    b_print_vertical(r, 0);

	Node_Key nk = btree_search(r, key);
	if (nk.node)
	{
		printf("\n===========key found(1): %d=========\n", key);
		for (i = 0; i < nk.node->n; ++i)
	        printf("%d  ", nk.node->key[i]);

        struct B_Tree_Node *p = nk.node->parent;
        if (p)
        {
    		printf("\n===========parent node found=========\n");
    		for (i = 0; i < p->n; ++i)
    	        printf("%d  ", p->key[i]);
        }
	}

    printf("\n===========test delete=========\n");
    for (i = 0; i < cnt; ++i)
    {
        printf("%d  ", d[i]);
        btree_delete(&r, d[i]);
    }

    printf("\n===========after delete=========\n");

    b_print_horizon(r, 0);

	nk = btree_search(r, key);
	if (nk.node)
	{
		printf("\n===========key found(2): %d=========\n", key);
		for (i = 0; i < nk.node->n; ++i)
	        printf("%d  ", nk.node->key[i]);

        struct B_Tree_Node *p = nk.node->parent;
        if (p)
        {
    		printf("\n===========parent node found=========\n");
    		for (i = 0; i < p->n; ++i)
    	        printf("%d  ", p->key[i]);
        }
	}

    btree_destroy(r);
    printf("\n===========test b_tree over=========\n");
}


/*******    test  Fibonacci Heap   start *********/
struct my_fibo_node
{
    long key;
    struct Fibo_Node f;
};

int my_fibo_cmp(struct Fibo_Node *n1, struct Fibo_Node *n2)
{
    struct my_fibo_node *mn1 = container_of(n1, struct my_fibo_node, f);
    struct my_fibo_node *mn2 = container_of(n2, struct my_fibo_node, f);
    return mn1->key - mn2->key;
}

bool my_fibo_decrease(struct Fibo_Node *n, void *key)
{
    struct my_fibo_node *mn = container_of(n, struct my_fibo_node, f);
    if (*(long*)key >= mn->key)
    {
        printf("\n========= my_fibo_decrease fail =========\n");
        return false;
    }
    mn->key = *(long*)key;
    printf("\n========= my_fibo_decrease ok =========\n");
    return true;
}

void fibo_heap_print(struct Fibo_Node *n, int indent)
{
    int i;

    if (!n)
        return;

    struct Fibo_Node *next = n;
    do
    {
        for (i = 0; i < indent; ++i)
            printf("    ");

        struct my_fibo_node *c = container_of(next, struct my_fibo_node, f);
        printf("%d(%d)  \n", c->key, next->degree);
        fibo_heap_print(next->child, indent+1);
    } while ((next = next->right) != n);
}


void test_fibo_heap()
{
    const int NUM = 1000, NUM2 = 100;
    int i, j = 0;
    struct Fibo_Heap *h = create_fibo_heap();
    struct my_fibo_node *dec[NUM2];

    printf("===========test_fibo_heap=========\n");

    for (i = 0; i < NUM; ++i)
    {
        struct my_fibo_node *n = malloc(sizeof(*n));
        n->key = rand()%100000;
        init_fibo_node(&n->f);
        fibo_heap_insert(h, &n->f, my_fibo_cmp);

        if (i % 3 == 0 && j < NUM2)
            dec[j++] = n;
    }

    fibo_heap_print(h->min, 0);

    printf("\n===========now do fibo_heap_extract_min=========\n");
    struct Fibo_Node *min = fibo_heap_extract_min(h, my_fibo_cmp);
    struct my_fibo_node *c = container_of(min, struct my_fibo_node, f);
    printf("minimun = %d\n", c->key);
    printf("------------------------\n");
    fibo_heap_print(h->min, 0);

    printf("\n===========test fibo_decrease_key=========\n");
    long key;
    for (j = 0; j < NUM2; ++j)
    {
        key = dec[j]->key >> 2;
        fibo_decrease_key(h, &dec[j]->f, &key, my_fibo_decrease, my_fibo_cmp);
    }
    fibo_heap_print(h->min, 0);

    printf("\n===========test fibo heap sort=========\n");
    while (min = fibo_heap_extract_min(h, my_fibo_cmp))
    {
        c = container_of(min, struct my_fibo_node, f);
        printf("%d  ", c->key);
    }
    printf("\n===========test fibo heap over===========\n");    
}
/*******    test  Fibonacci Heap   end *********/


void test_bp_tree()
{
    const int NUM = 10735;
    int d[NUM], cnt = 0;
    int i, j, key;
    BP_Tree_Node *r = bptree_create();
    BP_Tree_Node *h = r;

    printf("===========test insert B+-Tree=========\n");

    for (i = 0; i < NUM; ++i)
	{
		j = rand();
        bptree_insert(&r, j, NULL, BP_SKIP);

        if (i % 79 == 0)
            d[cnt++] = j;
    }
    printf("\n");

    printf("!!! link\n");
    bp_print_link(h);
    printf("!!! tree\n");
    bp_print_horizon(r, 0);

    printf("\n===========test delete B+-Tree=========\n");

    for (i = 0; i < cnt; ++i)
    {
        printf("delete %d\n", d[i]);
        bptree_delete(&r, d[i], BP_DATA_DELETE, NULL);

    }
    printf("\n");

    printf("!!! link\n");
    bp_print_link(h);
    printf("!!! tree\n");
    bp_print_vertical(r, 0);
}

void test_graph_bfs()
{
    Graph *g;
    char *vn[] = {"r", "s", "t", "u", "v", "w", "x", "y"};

    printf("=========== test graph BFS =========\n");

    create_graph(vn, sizeof(vn)/sizeof(vn[0]), G_UNDIRECTED, &g);

    add_edge(g, "v", "r");
    add_edge(g, "r", "s");
    add_edge(g, "s", "w");
    add_edge(g, "w", "t");
    add_edge(g, "w", "x");
    add_edge(g, "t", "x");
    add_edge(g, "t", "u");
    add_edge(g, "x", "u");
    add_edge(g, "x", "y");
    add_edge(g, "y", "u");

    Graph_ACT act = graph_bfs(g, "s");
    if (act == G_OK)
    {
        printf("path %s to %s:\n", "s", "v");
        print_bfs_path(g, "s", "v");
        printf("\n");
        printf("path %s to %s:\n", "s", "u");
        print_bfs_path(g, "s", "u");
        printf("\n");
        printf("path %s to %s:\n", "s", "y");
        print_bfs_path(g, "s", "y");
    }
    else
        printf("=========== test graph BFS fail!! =========\n");

    delete_graph(g);
    printf("\n=========== test graph BFS over =========\n");
}

void test_graph_dfs()
{
    Graph *g;
    char *vn[] = {"s", "t", "u", "v", "w", "x", "y", "z"};

    printf("=========== test graph DFS =========\n");

    create_graph(vn, sizeof(vn)/sizeof(vn[0]), G_DIRECTED, &g);

    add_edge(g, "z", "y");
    add_edge(g, "y", "x");
    add_edge(g, "x", "z");
    add_edge(g, "z", "w");
    add_edge(g, "w", "x");
    add_edge(g, "s", "z");
    add_edge(g, "s", "w");
    add_edge(g, "v", "s");
    add_edge(g, "v", "w");
    add_edge(g, "t", "v");
    add_edge(g, "t", "u");
    add_edge(g, "u", "v");

    Graph_ACT act = graph_dfs(g);
    if (act == G_OK)
    {
        printf("DFS forest: \n");
        print_dfs_forest(g);
    }
    else
        printf("=========== test graph DFS fail!! =========\n");

    delete_graph(g);
    printf("\n=========== test graph DFS over =========\n");
}

void test_strongly_conn_components()
{
    Graph *g, *tg = NULL;
    char *vn[] = {"a", "b", "c", "d", "e", "f", "g", "h"};

    printf("=========== test graph SCC =========\n");

    create_graph(vn, sizeof(vn)/sizeof(vn[0]), G_DIRECTED, &g);

    add_edge(g, "a", "b");
    add_edge(g, "b", "c");
    add_edge(g, "c", "d");
    add_edge(g, "d", "c");
    add_edge(g, "e", "a");
    add_edge(g, "b", "e");
    add_edge(g, "b", "f");
    add_edge(g, "c", "g");
    add_edge(g, "d", "h");
    add_edge(g, "e", "f");
    add_edge(g, "f", "g");
    add_edge(g, "g", "f");
    add_edge(g, "g", "h");
    add_edge(g, "h", "h");

    Graph_ACT act = strongly_conn_components(g, &tg);
    if (act == G_OK)
    {
        printf("strongly connection components: \n");
        print_dfs_forest(tg);
    }
    else
        printf("=========== test graph SCC fail!! =========\n");

    delete_graph(g);
    delete_graph(tg);
    printf("\n=========== test graph SCC over =========\n");
}


double undirected_weight_1(char *u, char *v)
{
    for (int i = 0; i < 2; ++i)
    {
        if (!strcmp(u, "a") && !strcmp(v, "b"))
            return 4;
        else if (!strcmp(u, "b") && !strcmp(v, "c"))
            return 8;
        else if (!strcmp(u, "c") && !strcmp(v, "d"))
            return 7;
        else if (!strcmp(u, "d") && !strcmp(v, "e"))
            return 9;
        else if (!strcmp(u, "e") && !strcmp(v, "f"))
            return 10;
        else if (!strcmp(u, "f") && !strcmp(v, "g"))
            return 2;
        else if (!strcmp(u, "g") && !strcmp(v, "h"))
            return 1;
        else if (!strcmp(u, "h") && !strcmp(v, "a"))
            return 8;
        else if (!strcmp(u, "b") && !strcmp(v, "h"))
            return 11;
        else if (!strcmp(u, "h") && !strcmp(v, "i"))
            return 7;
        else if (!strcmp(u, "i") && !strcmp(v, "c"))
            return 2;
        else if (!strcmp(u, "i") && !strcmp(v, "g"))
            return 6;
        else if (!strcmp(u, "c") && !strcmp(v, "f"))
            return 4;
        else if (!strcmp(u, "d") && !strcmp(v, "f"))
            return 14;
        else
        {
            char *tmp = u;
            u = v;
            v = tmp;
        }
    }
    return LLONG_MAX;
}

void test_kruskal_mst()
{
    Graph *g;
    char *vn[] = {"a", "b", "c", "d", "e", "f", "g", "h", "i"};

    printf("=========== test Kruskal mst =========\n");

    create_graph(vn, sizeof(vn)/sizeof(vn[0]), G_UNDIRECTED, &g);

    add_edge(g, "a", "b");
    add_edge(g, "b", "c");
    add_edge(g, "c", "d");
    add_edge(g, "d", "e");
    add_edge(g, "e", "f");
    add_edge(g, "f", "g");
    add_edge(g, "g", "h");
    add_edge(g, "h", "a");
    add_edge(g, "b", "h");
    add_edge(g, "h", "i");
    add_edge(g, "i", "c");
    add_edge(g, "i", "g");
    add_edge(g, "c", "f");
    add_edge(g, "f", "d");

    Queue *mst;
    Graph_ACT act = mst_kruskal(g, undirected_weight_1, &mst);
    if (act == G_OK)
    {
        printf("Minimum Spanning Tree: \n");
        print_kruskal_mst(mst);
    }
    else
        printf("=========== test Kruskal mst fail!! =========\n");

    delete_graph(g);
    delete_mst(mst);
    printf("\n=========== test Kruskal mst over =========\n");
}

void test_prim_mst()
{
    Graph *g;
    char *vn[] = {"a", "b", "c", "d", "e", "f", "g", "h", "i"};

    printf("=========== test Prim mst =========\n");

    create_graph(vn, sizeof(vn)/sizeof(vn[0]), G_UNDIRECTED, &g);

    add_edge(g, "a", "b");
    add_edge(g, "b", "c");
    add_edge(g, "c", "d");
    add_edge(g, "d", "e");
    add_edge(g, "e", "f");
    add_edge(g, "f", "g");
    add_edge(g, "g", "h");
    add_edge(g, "h", "a");
    add_edge(g, "b", "h");
    add_edge(g, "h", "i");
    add_edge(g, "i", "c");
    add_edge(g, "i", "g");
    add_edge(g, "c", "f");
    add_edge(g, "f", "d");

    char *root = "a";
    Graph_ACT act = mst_prim(g, undirected_weight_1, root);
    if (act == G_OK)
    {
        printf("Minimum Spanning Tree: \n");
        print_prim_mst(g, root);
    }
    else
        printf("=========== test Prim mst fail!! =========\n");

    delete_graph(g);
    printf("\n=========== test Prim mst over =========\n");
}

double directed_weight_1(char *u, char *v)
{
    if (!strcmp(u, "s") && !strcmp(v, "t"))
        return 6;
    else if (!strcmp(u, "t") && !strcmp(v, "x"))
        return 5;
    else if (!strcmp(u, "x") && !strcmp(v, "t"))
        return -2;
    else if (!strcmp(u, "z") && !strcmp(v, "x"))
        return 7;
    else if (!strcmp(u, "y") && !strcmp(v, "z"))
        return 9;
    else if (!strcmp(u, "s") && !strcmp(v, "y"))
            return 7;
    else if (!strcmp(u, "z") && !strcmp(v, "s"))
            return 2;
    else if (!strcmp(u, "t") && !strcmp(v, "y"))
            return 8;
    else if (!strcmp(u, "t") && !strcmp(v, "z"))
        return -4;
    else if (!strcmp(u, "y") && !strcmp(v, "x"))
        return -3;

    return LLONG_MAX;
}

void test_bellman_ford()
{
    Graph *g;
    char *vn[] = {"s", "t", "x", "y", "z"};

    printf("=========== test Bellman Ford =========\n");

    create_graph(vn, sizeof(vn)/sizeof(vn[0]), G_DIRECTED, &g);

    add_edge(g, "s", "t");
    add_edge(g, "t", "x");
    add_edge(g, "x", "t");
    add_edge(g, "z", "x");
    add_edge(g, "y", "z");
    add_edge(g, "s", "y");
    add_edge(g, "z", "s");
    add_edge(g, "t", "y");
    add_edge(g, "t", "z");
    add_edge(g, "y", "x");

    char *root = "s";
    Graph_ACT act = bellman_ford(g, directed_weight_1, root);
    if (act == G_OK)
    {
        printf("Bellman Ford single source shortest path: \n");
        print_single_source_shortest(g, root);
    }
    else
        printf("=========== test Bellman Ford fail!! =========\n");

    delete_graph(g);
    printf("\n=========== test Bellman Ford over =========\n");
}

double directed_weight_2(char *u, char *v)
{
    if (!strcmp(u, "s") && !strcmp(v, "t"))
        return 10;
    else if (!strcmp(u, "t") && !strcmp(v, "x"))
        return 1;
    else if (!strcmp(u, "x") && !strcmp(v, "z"))
        return 4;
    else if (!strcmp(u, "z") && !strcmp(v, "x"))
        return 6;
    else if (!strcmp(u, "y") && !strcmp(v, "z"))
        return 2;
    else if (!strcmp(u, "s") && !strcmp(v, "y"))
            return 5;
    else if (!strcmp(u, "z") && !strcmp(v, "s"))
            return 7;
    else if (!strcmp(u, "t") && !strcmp(v, "y"))
            return 2;
    else if (!strcmp(u, "y") && !strcmp(v, "t"))
        return 3;
    else if (!strcmp(u, "y") && !strcmp(v, "x"))
        return 9;

    return LLONG_MAX;
}

void test_dijkstra()
{
    Graph *g;
    char *vn[] = {"s", "t", "x", "y", "z"};

    printf("=========== test Dijkstra =========\n");

    create_graph(vn, sizeof(vn)/sizeof(vn[0]), G_DIRECTED, &g);

    add_edge(g, "s", "t");
    add_edge(g, "t", "x");
    add_edge(g, "x", "z");
    add_edge(g, "z", "x");
    add_edge(g, "y", "z");
    add_edge(g, "s", "y");
    add_edge(g, "z", "s");
    add_edge(g, "t", "y");
    add_edge(g, "y", "t");
    add_edge(g, "y", "x");

    char *root = "s";
    Graph_ACT act = dijkstra(g, directed_weight_2, root);
    if (act == G_OK)
    {
        printf("Dijkstra single source shortest path: \n");
        print_single_source_shortest(g, root);
    }
    else
        printf("=========== test Dijkstra fail!! =========\n");

    delete_graph(g);
    printf("\n=========== test Dijkstra over =========\n");
}

void test_linear_programming()
{
    double **A, *b, *c;
    const int M = 3, N = 3;
    int i, j;

    printf("=========== test Linear-Programming =========\n");

    A = malloc(M * sizeof(double*));
    for (i = 0; i < M; ++i)
        A[i] = malloc(N * sizeof(double));
    b = malloc(M * sizeof(double));
    c = malloc(N * sizeof(double));

    A[0][0] = 1; A[0][1] = 1; A[0][2] = 3;
    A[1][0] = 2; A[1][1] = 2; A[1][2] = 5;
    A[2][0] = 4; A[2][1] = 1; A[2][2] = 2;
    b[0] = 30; b[1] = 24; b[2] = 36;
    c[0] = 3; c[1] = 1; c[2] = 2;

    LG_Item r[M+N+1];
    LG_ACT act = simplex(M, N, A, b, c, r);
    if (act == LG_OK)
    {
        printf("\nlinear-programming ok!\n");
        for (i = 0; i < M+N+1; ++i)
            printf("%s=%f  ", r[i].name, r[i].value);
        printf("\n");
    }
    else
    {
        switch (act)
        {
        case LG_INVALID_PARAM:
            printf("fail: invalid param\n");
            break;
        case LG_INFEASIBLE:
            printf("fail: linear-programming is infeasible\n");
            break;
        case LG_UNBOUNDED:
            printf("fail: linear-programming is unbounded\n");
        }
    }

    printf("\n=========== test Linear-Programming over =========\n");
}

void test_KMP_matcher()
{
    printf("=========== test KMP_matcher =========\n");
    char t[] = "cababababcaa$RFddkfc,57e06AFFKcmbabacaewrwrababacadkff";
    char p[] = "ababaca";

    char m[sizeof(t)];
    KMP_matcher(t, strlen(t), p, strlen(p), sizeof(char), m);
    for (int i = 0; i < sizeof(m); ++i)
        if (m[i])
            printf("get match at: %d\n", i);

    printf("\n=========== test KMP_matcher over =========\n");
}

int main(int argc, char *argv[])
{
    srand(time(NULL));

    if (argc < 2)
    {
        printf("usage: test <test case>\n");
        return 0;
    }

    if (!strcmp(argv[1], "1"))
        test_merge_sort();
    else if (!strcmp(argv[1], "2"))
        test_max_subarray();
    else if (!strcmp(argv[1], "3"))
        test_heap_sort();
    else if (!strcmp(argv[1], "4"))
        test_heap_extract_max();
    else if (!strcmp(argv[1], "5"))
        test_heap_change_key();
    else if (!strcmp(argv[1], "6"))
        test_heap_insert();
    else if (!strcmp(argv[1], "7"))
        test_quick_sort();
    else if (!strcmp(argv[1], "8"))
        test_select_Ith();
    else if (!strcmp(argv[1], "9"))
        test_binary_tree();
    else if (!strcmp(argv[1], "10"))
        test_rb_tree();
    else if (!strcmp(argv[1], "11"))
        test_lcs();
    else if (!strcmp(argv[1], "12"))
        test_b_tree();
    else if (!strcmp(argv[1], "13"))
        test_fibo_heap();
    else if (!strcmp(argv[1], "14"))
        test_bp_tree();
    else if (!strcmp(argv[1], "15"))
        test_graph_bfs();
    else if (!strcmp(argv[1], "16"))
        test_graph_dfs();
    else if (!strcmp(argv[1], "17"))
        test_strongly_conn_components();
    else if (!strcmp(argv[1], "18"))
        test_kruskal_mst();
    else if (!strcmp(argv[1], "19"))
        test_prim_mst();
    else if (!strcmp(argv[1], "20"))
        test_bellman_ford();
    else if (!strcmp(argv[1], "21"))
        test_dijkstra();
    else if (!strcmp(argv[1], "22"))
        test_linear_programming();
    else if (!strcmp(argv[1], "23"))
        test_KMP_matcher();
    else
        printf("no such test\n");

    return 0;
}

